//
//  main.c
//  53. maxSubArray
//
//  Created by edz on 2020/7/8.
//  Copyright © 2020 edz. All rights reserved.
//


/*
 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

 示例:
 输入: [-2,1,-3,4,-1,2,1,-5,4],
 输出: 6
 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 
 进阶:
 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

 */
#include <stdio.h>

int maxSubArray(int* nums, int numsSize){
    int subsum = 0, maxsum = -2147483648;
    
    for(int i = 0; i < numsSize; i ++)
    {
        subsum += nums[i];
        if(subsum > maxsum)
        {
            maxsum = subsum;
        }
        if(subsum < 0)
            subsum = 0;
    }
    return maxsum;
}
